//: [Previous](@previous)

///极客时间算法课程练习

import Foundation

var str = "Hello, playground"

//: [Next](@next)

var arr = [4,2,3,5,9,6]
//在数组中查找key的位置
func find(array:[Int], count: Int, key:Int) -> Int {
    if array.count == 0 {
        return -1
    }
    var i = 0
    while i < count {
        if array[i] == key {
            return i
        }
        i += 1
    }
    return -1
}

func find2(array: inout [Int], count: Int, key:Int) -> Int {
    //边界条件处理
    if array.count == 0 {
        return -1;
    }
    //取出最后一个元素
    let temp = array.last!
    //用key替换掉最后一个元素
    array[count - 1] = key
    var i = 0
    //遍历对比
    while array[i] != key {
        i += 1
    }
    //复原数组
    array[count - 1] = temp
    if i == count - 1 {
        return -1
    }else {
        return i
    }
}
find(array: arr, count: arr.count, key: 9)
find2(array: &arr, count: arr.count, key: 7)


//测试链表
let testList = NodeList().appendToTail(1).appendToTail(2).appendToTail(3).appendToTail(4)

//翻转链表
func reversalList_1(_ list: NodeList) {
    let newList = NodeList()
    var node = list.head
    while node != nil {
        newList.appendToHead(node!.value)
        node = node!.next
    }
    print(newList)
}
reversalList_1(testList)




/*
 
 */
let loopList = NodeList()
let node_1 = Node(1)
loopList.appendNodeToTail(node_1)
let node_2 = Node(2)
loopList.appendNodeToTail(node_2).appendToTail(3).appendToTail(4)
let node_5 = Node(5)
loopList.appendNodeToTail(node_5)
node_5.next = node_1

//print(loopList)
print("aaa")

func checkLoop(_ list: NodeList) -> Bool {
    var slowNode = list.head
    var fastNode = list.head
    while slowNode != nil && fastNode != nil && fastNode!.next != nil {
        slowNode = slowNode!.next
        fastNode = fastNode!.next!.next
        print(slowNode, fastNode)
        if slowNode === fastNode {
            print("找到循环点")
            return true
        }
    }
    return false
}
checkLoop(loopList)



/* 递归
 假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？
 */
func f(_ n : Int) -> Int {
    if n == 1 {
        return 1
    }
    if n == 2 {
        return 2
    }
    return f(n - 1) + f(n - 2)
}
f(7)
